Thực đơn
Quy hoạch tuyến tính Dạng gia tố (Augmented form)(Các tài liệu trong nước gọi là đưa về dạng chính tắc)
Bài toán QHTT được biến đổi về dạng gia tố trước khi trước khi giải bằng thuật toán đơn hình (simplex algorithm). Trong dạng này có bổ sung một số "biến bù" không âm để biến các bất đẳng thức thành các đẳng thức. Khi đó bài toán viết dưới dạng:
Cực đại hóa Z trong: [ 1 − c T 0 0 A I ] [ Z x x s ] = [ 0 b ] {\displaystyle {\begin{bmatrix}1&-\mathbf {c} ^{T}&0\\0&\mathbf {A} &\mathbf {I} \end{bmatrix}}{\begin{bmatrix}Z\\\mathbf {x} \\\mathbf {x} _{s}\end{bmatrix}}={\begin{bmatrix}0\\\mathbf {b} \end{bmatrix}}} x , x s ≥ 0 {\displaystyle \mathbf {x} ,\,\mathbf {x} _{s}\geq 0}trong đó xs là các biến bù, còn Z là biến cần cực đại.
Bài toán trong ví dụ trên sau khi biến đổi có dạng:
Cực đại hóa | S 1 x 1 + S 2 x 2 {\displaystyle S_{1}x_{1}+S_{2}x_{2}\,} =Z | (hàm mục tiêu) |
với các ràng buộc | ||
x 1 + x 2 + x 3 = A {\displaystyle x_{1}+x_{2}+x_{3}=A\,} | (ràng buộc gia tố) | |
F 1 x 1 + F 2 x 2 + x 4 = F {\displaystyle F_{1}x_{1}+F_{2}x_{2}+x_{4}=F\,} | (ràng buộc gia tố) | |
P 1 x 1 + P 2 x 2 + x 5 = P {\displaystyle P_{1}x_{1}+P_{2}x_{2}+x_{5}=P\,} | (ràng buộc gia tố) | |
x 1 , x 2 , x 3 , x 4 , x 5 ≥ 0 {\displaystyle x_{1},x_{2},x_{3},x_{4},x_{5}\geq 0} |
trong đó x 3 , x 4 , x 5 {\displaystyle x_{3},x_{4},x_{5}\,} là các "biến bù" không âm.
Nó có thể viết dưới dạng ma trận:
Cực đại hóa Z trong: [ 1 − S 1 − S 2 0 0 0 0 1 1 1 0 0 0 F 1 F 2 0 1 0 0 P 1 P 2 0 0 1 ] [ Z x 1 x 2 x 3 x 4 x 5 ] = [ 0 A F P ] , [ x 1 x 2 x 3 x 4 x 5 ] ≥ 0 {\displaystyle {\begin{bmatrix}1&-S_{1}&-S_{2}&0&0&0\\0&1&1&1&0&0\\0&F_{1}&F_{2}&0&1&0\\0&P_{1}&P_{2}&0&0&1\\\end{bmatrix}}{\begin{bmatrix}Z\\x_{1}\\x_{2}\\x_{3}\\x_{4}\\x_{5}\end{bmatrix}}={\begin{bmatrix}0\\A\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\x_{4}\\x_{5}\end{bmatrix}}\geq 0}Thực đơn
Quy hoạch tuyến tính Dạng gia tố (Augmented form)Liên quan
Quy Quy ước giờ mùa hè Quy Nhơn Quyền Anh Quyền lực phân lập Quy tắc chia hết Quyền Linh Quyền LGBT của các quốc gia, vùng lãnh thổ Quyền riêng tư trên Internet Quyền LGBT ở Hoa KỳTài liệu tham khảo
WikiPedia: Quy hoạch tuyến tính